|
NC21 链表内指定区间反转
描述 将一个链表\ m m 位置到\ n n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 例如： 给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4, 返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL. 注意： 给出的 mm,nn 满足以下条件： 1 \leq m \leq n \leq 链表长度1≤m≤n≤链表长度 示例1 输入： {1,2,3,4,5},2,4 复制 返回值： {1,4,3,2,5}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
ListNode dummy = new ListNode(0) ;
dummy.next = head ;
ListNode curt = dummy ;
for(int i = 0 ; i
return head ;
}
}
ListNode nm = curt.next ;
ListNode nn = dummy;
for(int i = 0 ; i
return head ;
}
}
ListNode nnplus = nn.next ;
ListNode prev = curt ;
ListNode tail = nm ;
while(tail != nnplus){
ListNode temp = tail.next ;
tail.next = prev ;
prev = tail ;
tail = temp ;
}
nm.next = nnplus ;
curt.next = nn ;
return dummy.next;
}
}
|